package union_find_set;

import java.util.Arrays;


class Solution {
    public boolean equationsPossible(String[] equations) {
        unionFindSet unionfindset = new unionFindSet(26);
        for (int i = 0; i < equations.length; i++) {
            if (equations[i].charAt(1) == '=') {
                unionfindset.union(equations[i].charAt(0) - 'a', equations[i].charAt(3) - 'a');
            }
        }
        for (int i = 0; i < equations.length; i++) {
            if (equations[i].charAt(1) != '=') {
                // 不等号的两个数其实是一个圈子的
                if (unionfindset.isSameFindSet(equations[i].charAt(0) - 'a', equations[i].charAt(3) - 'a')) {
                    return false;
                }
            }
        }
        return true;

    }
}

public class unionFindSet {
    int[] array;

    public unionFindSet(int num) {
        array = new int[num];
        // 初始化为-1
        Arrays.fill(array, -1);
    }


    public boolean isSameFindSet(int a, int b) {
        return findRoot(a) == findRoot(b);
    }

    private int findRoot(int a) {
        //如果下标负数,则违法抛出异常
        if (a < 0) {
            throw new ArrayIndexOutOfBoundsException();
        }
        while (array[a] >= 0) {
            a = array[a];
        }
        return a;
    }

    public boolean union(int x1, int x2) {
        //合并两个数要合并根结点
        //先要判断是不是同一集合
        int root1 = findRoot(x1);
        int root2 = findRoot(x2);
        if (root1 == root2) {
            System.out.println("属于同一集合,不需要合并");
            return false;
        }
        array[root1] += array[root2];
        array[root2] = root1;
        return true;
    }

    public int getSet() {
        int count = 0;
        for (int x : array) {
            if (x < 0) {
                count++;
            }
        }
        return count;
    }

    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int n = 10;
        int m = 3;
        int p = 2;

        unionFindSet unionFindSet = new unionFindSet(n);

        System.out.println("合并：0和6：");
        unionFindSet.union(0, 6);
        unionFindSet.union(0, 1);
        System.out.println("合并：3和7：");
        unionFindSet.union(3, 7);
        System.out.println("合并：4和8：");
        unionFindSet.union(4, 8);

        System.out.println("以下是不是亲戚：");
        boolean flg = unionFindSet.isSameFindSet(1, 8);
        if (flg) {
            System.out.println("是亲戚！");
        } else {
            System.out.println("不是亲戚！");
        }
        System.out.println("当亲的亲戚关系 " + unionFindSet.getSet() + " 对！");
    }

    public static void main1(String[] args) {
        unionFindSet unionFindSet = new unionFindSet(10);
        System.out.println("合并：0和6：");
        unionFindSet.union(0, 6);
        System.out.println("合并：0和7：");
        unionFindSet.union(0, 7);
        System.out.println("合并：0和8：");
        unionFindSet.union(0, 8);

        System.out.println("合并：1和4：");
        unionFindSet.union(1, 4);
        System.out.println("合并：1和9：");
        unionFindSet.union(1, 9);
        System.out.println("合并：2和3：");
        unionFindSet.union(2, 3);

        System.out.println("合并：2和5：");
        unionFindSet.union(2, 5);

        unionFindSet.print();

        System.out.println("合并：8和1：");
        unionFindSet.union(8, 1);

        unionFindSet.print();

        System.out.println("查找是不是同一个集合");
        System.out.println(unionFindSet.isSameFindSet(6, 9));
        System.out.println(unionFindSet.isSameFindSet(8, 2));
    }
}
